package Top200;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2022-02-27 17:13
 * 中序遍历升序，找到两个被交换的节点
 */
public class recoverTree99 {
    TreeNode first=null,second=null,pre=new TreeNode(Integer.MIN_VALUE);
    void inorder(TreeNode root){
        if (root==null)  return;
        inorder(root.left);
        if (root.val< pre.val){
            if (first==null){
                first=pre;
            }
            second=root;
        }
        pre=root;
        inorder(root.right);
    }
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp=first.val;
        first.val=second.val;
        second.val=temp;
    }
}
